package Graph;

import com.sun.corba.se.impl.orbutil.graph.Graph;

import java.util.*;

public class Test {
    /*图的难点并不在于算法
    * 而在于图的表现形式太多,而每一个表现形式所对应的这种算法,实现起来也是不一样的
    * 所以一个好的解决方法就是:你只用一种图的表现形式来实现所有图的算法,之后遇到图的不同
    * 表现形式的时候,你只需要提供一个接口函数,将那个不熟悉的图的表现形式转换为你熟悉的图结构即可*/

    /*这个类主要是:用来写接口函数,与常见图的算法*/


    /*图的广度优先遍历
    *  1利用队列实现,从给定节点依次按照宽度进队列,然后弹出
    *  2每弹出一个点,就把该节点所有没有进过队列的临接点,放入队列*/


    //图的广度优先遍历与二叉树的宽度优先遍历的不同点在于,图是可能有环的
    public static void BFS(Node node){
        if (node == null)return;
        Queue<Node> queue= new LinkedList<>();
        HashSet<Node> hashSet=new HashSet<>();
        //set为队列服务,保证每一个点不重复进入,避免成环
        queue.add(node);
        hashSet.add(node);

        while (!queue.isEmpty()){
            Node cur = queue.poll();

            System.out.println(cur.value);
            //这个输出语句代表你要对这个数据进行的操作

            for(Node next : cur.nexts){
                /*这个循环代表者,把这个节点的所有临接点都进去*/
                if (!hashSet.contains(next)){
                    queue.add(next);
                    hashSet.add(next);
                }
            }
        }
    }




    /*图的深度优先遍历
    * 1利用栈实现,从给定节点开始把节点按照深度依次放入栈,然后弹出
    * 2每弹出一个点,就把这个节点下一个没有进过栈的临接点放入栈中
    * 3直到栈空*/
    public static void DFS(Node node){
        if (node == null)return;
        Stack<Node> stack=new Stack<>();
        HashSet<Node> set=new HashSet<>();
        /*这个栈永远保持这个深度优先的路径*/
        /*这个set表示有没有走过,去重*/
         stack.add(node);
         set.add(node);
        System.out.println(node.value);
         while (!stack.isEmpty()){
             Node cur =stack.pop();
             for (Node next : cur.nexts){
                 if (!set.contains(next)){
                     /*注意这里的细节,当邻居不在表set中,就要把原来的节点也要重新押入栈
                     * 在把邻居压入栈中,表中*/
                     stack.push(cur);
                     stack.push(next);
                     set.add(next);
                     System.out.println(next.value);
                     //输出语句同样可以换成别的数据操作语句
                     break;
                     //压入进去后,直接返回,继续查询
                 }
             }
         }
    }

    /*拓扑排序算法
    * 思想: 先找一个入度为0的点,记录下来,然后消除这个点的所有影响
    * 在重复上述过程*/
    public static List<Node> sortedTopolgy(GrapH graph){
        //key 某一个node
        //value 剩余的入度
        HashMap<Node,Integer> inMap=new HashMap<Node, Integer>();
        /*入度为0的进队列*/
        Queue<Node> zeroInQueue =new LinkedList<Node>();
        for (Node node : graph.nodes.values()){
            /*将每个点都作为单独的一个集合,进入map,*/
            inMap.put(node, node.in);
            if (node.in == 0){

                zeroInQueue.add(node);
            }
        }
        List<Node> result=new LinkedList<>();
        while (!zeroInQueue.isEmpty()){
            Node cur=zeroInQueue.poll();
            result.add(cur);
            for (Node next : cur.nexts){
                inMap.put(next,inMap.get(next)-1);
                if (inMap.get(next) == 0){
                    zeroInQueue.add(next);
                }
            }
        }
        return result;
    }
    /*最小生成树
    * 思路
    * k算法的思路是:每次都找最小的边,然后如果这个边不形成环路的话就连接起来,如果会就不加 */
  public static Set<Edge> kruskalMST(GrapH grapH){
        /*unionFind 代表实现的一种并查集*//*
        UnionFind unionFind=new UnionFind();
        unionFind.makeSets(grapH.nodes.values());//初始化
        PriorityQueue<Edge> priorityQueue=new PriorityQueue<>();
        //将每一条边权值入队
        for (Edge edge : grapH.edges){
            priorityQueue.add(edge);
        }
        Set<Edge> result=new HashSet<Edge>();
      *//*形成一个结果集*//*
        while (!priorityQueue.isEmpty()){
            Edge edge=priorityQueue.poll();
            if (!unionFind.isSameSet(edge.from,edge.to)){//如果并查集中不成环路就加入到结果集中
                result.add(edge);
                unionFind.union(edge.from,edge.to);//如果入队后,就将俩个点集合到一起.
            }
        }
        return result;*/
      return new HashSet<>();
    }
    public static Set<Edge> primMST(GrapH grapH){
        //解锁的边放到小跟堆里面去
        PriorityQueue<Edge> priorityQueue=new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1,Edge o2) {
                return o1.weight-o2.weight;
            }
        });
        //考察过的点都放入set中
        HashSet<Node> set=new HashSet<Node>();
        Set<Edge> result = new HashSet<>();
        for (Node node : grapH.nodes.values()){//防止图不是连通的情况(如果是连通的这个for就没必要写)
            //node是开始点
            if (!set.contains(node)){
                set.add(node);
                for (Edge edge : node.edges){
                    priorityQueue.add(edge);//由一个边解锁所有的边
                }
                while (!priorityQueue.isEmpty()){
                    Edge edge =priorityQueue.poll();//弹出最小的边
                    Node toNode = edge.to;//可能是一个新的点
                    if (!set.contains(toNode)){//不含的话,就是新的点
                        set.add(toNode);
                        result.add(edge);
                        for (Edge nextEdge :toNode.edges){//将新的点的边都放到队列中
                            priorityQueue.add(nextEdge);
                        }
                    }
                }
            }
        }
        return result;
    }
















}
